package xyz.scootaloo.code.collection

import org.junit.Test
import xyz.scootaloo.code.adt.BinarySearchTree
import xyz.scootaloo.code.common.pause

/**
 * @author flutterdash@qq.com
 * @since 2021/11/11 14:45
 */

class BinarySearchTreeTest {
    @Test
    fun process1() {
        /**
         *     2             2
         *   /   \    =>   /
         *  1    (3)      1
         */
        val tree = BinarySearchTree<Int>()
        tree.add(2)
        tree.add(1)
        tree.add(3)
        pause()
        tree.remove(3)
        pause()
    }

    @Test
    fun process2() {
        /**
         *    (2)           3
         *   /   \    =>   /
         *  1     3       1
         */
        val tree = BinarySearchTree<Int>()
        tree.add(2)
        tree.add(1)
        tree.add(3)
        pause()
        tree.remove(2)
        pause()
    }

    @Test
    fun process3() {
        /**
         *      2
         *    /   \
         *   1    (5)
         *       /  \
         *      3    6
         *       \
         *        4
         */
        val tree = BinarySearchTree<Int>()
        tree.add(2)
        tree.add(1)
        tree.add(5)
        tree.add(3)
        tree.add(6)
        tree.add(4)
        pause()
        tree.remove(5)
        pause()
    }

    @Test
    fun process4() {
        /**
         *     (2)               3               3
         *    /   \            /   \           /   \
         *   1     5          1     5         1     5
         *       /  \    =>        /  \   =>      /   \
         *      3    6            2    6         4     6
         *       \                 \
         *        4                 4
         */
        val tree = BinarySearchTree<Int>()
        tree.add(2)
        tree.add(1)
        tree.add(5)
        tree.add(3)
        tree.add(6)
        tree.add(4)
        pause()
        tree.remove(2)
        pause()
    }
}
